package algorithm.util;


public class BigInteger implements Comparable {
	
	private int[] _digits;
	
	public BigInteger(String s) {
		
		this._digits = this._remove_prefix_zero(this._str2num(s));
	}
	
	private BigInteger(int[] s) {
		
		this._digits = s;
	}

	private String _num2str(int[] a) {
		
		String s = "";
		for (int i = a.length-1; i > -1; i --) {
			s += a[i];
		}
		return s;
	}

	private int[] _str2num(String s) {

		if (s == null || s.trim().length() == 0) {
			return null;
		} else {
			s = s.trim();
			int len = s.length();
			int[] n = new int[len];
			for (int i = 0; i < len; i ++) {
				n[i] = Integer.valueOf(s.substring(len-i-1, len-i));
			}
			return n;
		}
	}
	
	/**
	 * r^n
	 * @param r
	 * @param n
	 * @return
	 */
	private int[] _pow(int[] r, int n) {
		
		if (n == 0) {
			return new int[] {1};
		} else if (n == 1) {
			return r;
		} else {
			int[] ret = r;
			for (int i = 1; i < n; i ++) {
				ret = _mul(ret, r);
			}
			return ret;
		}
	}
	
	public BigInteger pow(int n) {
		return new BigInteger(this._pow(this._digits, n));
	}
	
	public BigInteger mul(BigInteger t) {
		return new BigInteger(this._mul(this._digits, t._digits));
	}
	
	public BigInteger add(BigInteger t) {
		return new BigInteger(_add(this._digits, t._digits));
	}

	private int[] _mul(int[] s, int[] t) {
		
		if (s == null || s.length == 0) {
			s = new int[] {0};
		}
		if (t == null || t.length == 0) {
			t = new int[] {0};
		}
		int[] r = new int[s.length + t.length];
		int c, m, d;
		
		c = 0;
		for (int i = 0; i < t.length; i ++) {
			c = 0;
			for (int j = 0; j < s.length; j ++) {
				m = t[i] * s[j];
				d = r[i+j] + m + c;
				r[i+j] = d%10;
				c = d/10;
			}
			if (c > 0) {
				r[i+s.length] += c;
			}
		}
		
		return _remove_prefix_zero(r);
	}
	
	private int[] _remove_prefix_zero(int[] r) {
		
		//remove prefix zero
		int idx = 0;
		for (idx = r.length-1; idx > -1; idx--) {
			if (r[idx] != 0) {
				break;
			}
		}
		if (idx == -1) {
			int[] rr = new int[1];
			rr[0] = 0;
			return rr;
		} else {
			int[] rr = new int[idx+1];
			for (int i = 0; i <= idx; i ++) {
				rr[i] = r[i];
			}
			return rr;
		}
	}
	
	private int[] _add(int[] s, int[] t) {
		
		if (s == null || s.length == 0) {
			s = new int[] {0};
		}
		if (t == null || t.length == 0) {
			t = new int[] {0};
		}
		int len = Math.max(s.length, t.length)+1;
		int[] r = new int[len];
		int c = 0, d = 0;
		for (int i = 0; i < len; i ++) {
			d = c;
			d += (i < s.length)?s[i]:0;
			d += (i < t.length)?t[i]:0;
			r[i] = d%10;
			c = d/10;
		}
		return this._remove_prefix_zero(r);
	}
	
	@Override
	public String toString() {
		return this._num2str(this._digits);
	}

	public int compareTo(Object obj) {
		
		if (obj == null || !BigInteger.class.isAssignableFrom(obj.getClass())) {
			throw new RuntimeException("Wrong Number!");
		} else {
			BigInteger num = (BigInteger)obj;
			return this._compare(this._digits, num._digits);
		}
	}

	private int _compare(int[] x, int[] y) {
		
		if (x.length < y.length) {
			return -1;
		} else if (x.length > y.length) {
			return 1;
		} else {
			for (int i = x.length-1; i > -1; i --) {
				if (x[i] > y[i]) {
					return 1;
				} else if (x[i] < y[i]) {
					return -1;
				}
			}
			return 0;
		}
	}
}
